// 给定一个数组nums，要求计算出数组中的逆序对的总数
// 逆序对：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对

// 解法1： 归并排序
// 归并排序分为 分解过程和 合并过程，其中合并过程实质上是两个有序数组的合并过程
// 我们在合并两个有序数组的时候计算逆序对
// 1. 使用全局变量cnt存储逆序对的个数，然后进行归并排序
// 2. 分割过程，递归的将当前序列平均分成两半，直到子序列长度为1
// 3. 归并过程，从长度为1的子序列开始，依次进行两两归并，直到合并成一个长度为n的有序序列
// 4. 在合并有序序列的过程中，记录当前左子序列中元素和右子序列元素所形成的逆序对个数，并累加到cnt中

let cnt = 0
function merge(leftArr, rightArr) {
    let arr = []
    let leftIndex = 0
    let rightIndex = 0
    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        if (leftArr[leftIndex] <= rightArr[rightIndex]) {
            arr.push(leftArr[leftIndex])
            leftIndex++
        } else {
            cnt += leftArr.length - leftIndex
            arr.push(rightArr[rightIndex])
            rightIndex++
        }
    }
    if (leftIndex < leftArr.length) {
        arr = [...arr, ...leftArr.slice(leftIndex)]
    }
    if (rightIndex < rightArr.length) {
        arr = [...arr, ...rightArr.slice(rightIndex)]
    }
    return arr
}

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let mid = Math.floor(arr.length / 2)
    let leftArr = mergeSort(arr.slice(0, mid))
    let rightArr = mergeSort(arr.slice(mid))
    return merge(leftArr, rightArr)
}

let arr = [7, 5, 6, 4];
mergeSort(arr)
console.log(cnt)
